Sparsely populated data sets are utilized in numerous technical fields. The present invention was developed for efficiently encoding image data that has been transformed by successive applications of wavelet transforms or discrete cosine transforms (DCT), but is equally applicable to other types of sparsely populated data sets. Image data that has been transformed by successive applications of these transforms tends to have large portions occupied by zero and near-zero values, especially if the data is subjected to a data quantization step prior to encoding. Prior art encoding techniques include methods that require all the transform coefficients for an image to be processed together. These techniques require large amounts of memory and are therefore ill-suited for smaller electronic image equipment such as digital cameras.
The primary goals of the present invention are to provide an encoding methodology that (A) encodes wavelet and DCT data with as few data bits as possible, (B) determines the maximum number of data bits required to encode sub-arrays that include at least some non-zero data, and (C) encodes non-zero data with the minimum number of data bits required to losslessly store such data.
Other goals of the present invention are to provide an encoding methodology that uses memory very efficiently, and one that is suitable for implementation in a range of different hardware (i.e., electronic circuitry).